// 如果没有定义过 COMPETITION_TEMPLATE_HPP 这个宏，就往下执行。
#ifndef COMPETITION_TEMPLATE_HPP
#define COMPETITION_TEMPLATE_HPP

// --------------------- 基础头文件 ---------------------
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <list>
#include <cmath>
#include <numeric>    // gcd, lcm, accumulate
#include <functional> // greater, less
#include <utility>    // pair, swap
#include <tuple>      // tuple
#include <iomanip>    // 输出格式控制
#include <cassert>    // assert
#include <climits>
#include <cstring>

using namespace std;

// --------------------- IO 优化 ---------------------
#define fastio                   \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr)
#define endl "\n" // 避免 endl 带来的 flush

// --------------------- 宏简写 ---------------------
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, a, b) for (int i = (a); i < (b); i++)  // [a, b)
#define per(i, a, b) for (int i = (a); i >= (b); i--) // 从 a 到 b 递减
#define each(x, v) for (auto &x : v)                  // 遍历容器
#define show(x) cout << x << endl

// --------------------- 类型别名 ---------------------
using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using vi = std::vector<int>;
using vll = std::vector<ll>;

// --------------------- 常用函数 ---------------------
template <typename T>
inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

template <typename T>
inline T lcm(T a, T b) { return a / gcd(a, b) * b; }

inline ll qpow(ll a, ll b, ll mod)
{ // 快速幂 (a^b % mod)
    ll res = 1;
    a %= mod;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// --------------------- 调试工具（可选，赛时可删） ---------------------
#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << endl
#else
#define debug(x)
#endif

#endif // COMPETITION_TEMPLATE_HPP